Closest binary search tree value

Time: O(H); Space: O(1); easy

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Given target value is a floating point.

You are guaranteed to have only one unique value in the BST that is closest to the target.

Example 1:

    5
   / \
  4    9
 /    / \
2    8  10

Input: root = {TreeNode} [5,4,9,2,#,8,10], target = 6.124780

Output: 5

Example 1:

    3
   / \
  2    4
 /
1

Input: root = {TreeNode} [3,2,4,1] and target = 4.142857

Output: 4

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[2]:

class Solution1(object):
    """
    Time: O(H)
    Space: O(1)
    """
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        gap = float("inf")
        closest = float("inf")

        while root:
            if abs(root.val - target) < gap:
                gap = abs(root.val - target)
                closest = root.val
            if target == root.val:
                break
            elif target < root.val:
                root = root.left
            else:
                root = root.right
        return closest

[3]:

s = Solution1()

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)
target = 6.124780
assert s.closestValue(root, target) == 5

root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.left.left = TreeNode(1)
target = 4.142857
assert s.closestValue(root, target) == 4